// https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/
// Created by ade on 2022/8/11.
// 二叉搜索树
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 自己的解法数组加二叉树搜索搜索 这个解法比官方还快一点。。。
    bool flag = false;

    vector<int> nums;

    bool findTarget1(TreeNode *root, int k) {
        getData(root);
        for (auto i :nums) {
            dfs(root, i, k);
            if (flag) return true;
        }
        return false;
    }

    void dfs(TreeNode *node, int pre, int k) {
        if (!node) return;
        if (node->val != pre && pre + node->val == k) {
            flag = true;
            return;
        }
        if (pre + node->val > k) {
            dfs(node->left, pre, k);
        } else {
            dfs(node->right, pre, k);
        }
    }

    void getData(TreeNode *node) {
        if (!node) return;
        nums.push_back(node->val);
        getData(node->left);
        getData(node->right);
    }

    // 官方解法
    unordered_map<int, int> m = {};

    bool findTarget(TreeNode *root, int k) {
        return findSum(root, k);
    }

    bool findSum(TreeNode *root, int k) {
        if (!root) return false;
        if (m.count(k - root->val) > 0)return true;
        m.insert({root->val, 1});
        return findSum(root->left, k) || findSum(root->right, k);
    }
};

int main() {
    Solution so;
    TreeNode *h1 = so.init();
    auto res = so.findTarget(h1, 9);
    if (res)cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}
